1. Field of the Invention
This invention relates to processors for computer systems, and more particularly, to the processing of branch instructions in processors.
2. Description of the Related Art
Modern processors for computer systems and other devices use a number of different techniques to increase the throughput of executed instructions, and thus achieve higher performance. Pipelining is one such technique, wherein multiple instructions may each be at different stages of execution (i.e. in different stages of a pipeline) in a given instance. Typical pipeline stages may include a number of stages, each of which performs a function of the pipeline, such as fetching instructions, decoding instructions, fetching operands, executing instructions, and writing results of the executed instructions to memory (e.g., to registers).
Additional techniques may be employed in order to keep the pipeline full and to prevent stalls. Two related techniques that may be utilized are branch prediction and speculative execution. Branch prediction may be used to predict the results of an upcoming branch instruction in an instruction stream. A branch instruction is an instruction that may alter the flow of instructions based on a certain condition. If the condition is true, the instruction flow may be altered (i.e. the branch is taken), whereas a next instruction in the sequence may be executed if the condition is false (i.e. the branch is not taken). A branch prediction unit may be utilized in a processor in order to predict whether or not branches in upcoming branch instructions are taken or not taken.
In conjunction with branch prediction, speculative execution may also be utilized. Based on the result of the prediction by a branch prediction unit, instructions following the branch instruction may be executed. For example, if a branch prediction unit predicts that a branch will be taken, instructions corresponding to the taken branch may be speculatively executed. If the branch was correctly predicted, the results of the speculatively executed instructions may be committed to registers, with those instructions being subsequently retired. Thus, correctly predicting the results of branch instructions may prevent stalls in the pipeline while awaiting evaluation of the condition upon which the direction of the branch is based.
In the event that a branch prediction is incorrect (i.e. mispredicted), the results of instructions that were speculatively executed based on the mispredicted branch may be discarded. The instructions corresponding to the other direction of the branch (i.e. those instructions that would have been executed had the branch been correctly predicted) may be dispatched and subsequently executed. A misprediction may result in a stall in the pipeline, and thus a performance penalty. In many cases however, this performance penalty may be acceptable if the ratio of correctly predicted branches to mispredicted branches is of a sufficiently high value.